<?php

/**快速排序  获取数组的第一个值，其他值和这个值比较,生成 左段比这个值小，右端比这个值大，递归遍历两段
时间复杂度f(n)= D(n)+f(i1)+f(i2)
 其中 D(n)=n-1,是一趟快排需要的比较次数，一趟快排结束后将数组分成两部分 [公式] 和 [公式]
核心点:最好情况下，每一次划分都正好将数组分成长度相等的两半
f(n)= D(n)+f(n/2)+f(n/2)=D(n)+2D(n/2)+4T(n/4)=n-1+2(n/2-1)+...+2^k(n/2^k-1)
=n-1+n-2+n-4+...+n-2^k = nlog2^n
=O(nlog2^n)
k=log2^n
2^k=n
核心点:最坏情况下，每一次划分都将数组分成了0和n-1两部分
最坏时间复杂度f(n)=n^2-n/2=O(n^2)
*/
function quickSort($arr) {
	if(count($arr) <= 1) {
		return $arr;
	}
	$comp = array_shift($arr);
	$a = array();
	$b = array();
	foreach($arr as $v) {
	$v <= $comp ? $a[] = $v : $b[] = $v;
	}
	$a = quickSort($a);
	$b = quickSort($b);
	return array_merge($a,array($comp),$b);
}

/**
快速排序2，交换排序 获取一个值,依次左右比较 从右比较小的值,放在左边,在从左边下一个比较,大的值放在右边
 * 再对左右两段排序
 * 因为每次只有一个位置空闲
*1.获取数组的随机一个值(默认第一个值)prior，定义start=0，end=n-1
*2.从右向左 end--找到第一个比prior小的值，移动到左边且start++，此时的end的位置还是原来的值，但是用来存储比prior大的值,没有找到，则start=end，结束循环
*3.从左start的位置向右查start++第一个比prior大的值，移动到右边end的位置，如果没有找到，则start=end，结束循环
*4.结束循环时start=end，将start的位置值设为prior，然后pior将左边和右边的位置在分别排序

*/
function cQuick(&$arr,  $start, $end) {
	if ($start>=$end) {
		return;
	}
    $high =  $end;
	$prior = $arr[$start];
	$low =  $start;
	while($low<$high) {
		while($low<$high && $arr[$high]>= $prior) {
			$high--;
		}
		if ($low<$high) {
			$arr[$low] = $arr[$high]; //将小值放在low位置,high值是空的
			$low++;
		}
		
		while ($low<$high && $arr[$low] <= $prior) {
			$low++;
		}
		if ($low<$high) {
            $arr[$high] = $arr[$low];
            $high--;
		}
		//var_dump($arr, $low, $high);
	}
	$arr[$low] = $prior;
	cQuick($arr, 0, $low-1);
	cQuick($arr, $low+1, $end);
}

/**交换排序1 冒泡排序、下沉排序 N个元素
 * 遍历数组，依次对比相邻的值，大的下沉，小的上浮，因为是对比相邻，且下标到最大，
 * 第一轮排序后,最大的下沉到最末尾元素 比较了N-1次
 * 第二轮继续下沉倒数第二
 * 第N-1轮  比较第一个和第二个元素,下沉到第2个元素,只剩下1个元素,后面就不需要排序了
 * 时间复杂度f(n)= 1+2+3+....+n-1 = n^2-n/2
 * 1,2,3是每轮是比较的次数
*/
function bubble($arr) {
	$count = count($arr);
	for ($i=$count-1;$i>0;$i--) {
		for($y=0;$y<$i;$y++) {
			if($arr[$y] > $arr[$y+1]) {
				$t = $arr[$y];
				$arr[$y] =$arr[$y+1];
				$arr[$y+1] = $t;
			}
		}
	}
	return $arr;
}

/**交换排序2 选择排序
 * 遍历数组,对比当前位置元素和剩余值，当前值大，交换值，
 * 第一轮，比较第一个元素和其他元素 排序后得到第一个元素值最小
 * 第二轮,选取第二个元素 比较后面的元素,排序后得到第二个最小的元素
 * 第N-1轮,比较第N-1个元素和最后一个第N元素,得到排序号的数组
 时间复杂度f(n)= 1+2+3+....+n-1 =  n^2-n/2
*/
function changesort($arr) {
	$count = count($arr);
	for ($i=0;$i<$count;$i++) {
		for($y=$i+1;$y<$count;$y++) {
			if($arr[$i] > $arr[$y]) {
				$t = $arr[$i];
				$arr[$i] = $arr[$y];
				$arr[$y] = $t;
			}
		}
	}
	return $arr;
}

/*
 * 归并排序
 * 对半拆分，无限拆分成单元素，相邻的两个元素排序 子序列先合并排序，最终的有序对半序列在合并排序
 * 时间复杂度和快速排序一样，但是归并排序更稳定，因为她是先排序在合并，没有那么大的随机性
 * 假设 相邻的元素排序是一轮 第一轮是 n/2 次比较
 * 第二轮是 相邻的2个元素和相邻的两个元素排序
*/
function mergeSort($arr) {
  $len = count($arr);
  if (1 == $len) {
  	return $arr;
  }
  $left = array_slice($arr, 0, intval($len/2));
  $right = array_slice($arr,intval($len/2));

  $left = mergeSort($left);
  var_dump($left,$right);
  $right = mergeSort($right);

  $arr = mergeArr($left, $right);
  return $arr;
}

//合并已排序的数组
function mergeArr($left, $right) {
	while (0 < count($left) && 0 < count($right)) {
		if ($left[0]< $right[0]) {
			$result[] = array_shift($left);
		} else {
			$result[] = array_shift($right);
		}
	}
	$result = array_merge($result, $left, $right);
	return $result;
}

/**
* 插入排序 将一个记录插入到已经排好序的有序表中
1.第一个元素，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描,和这个元素比较
 * 这个元素小于排序的元素，将排序的元素相后移动，直到找到已排序的元素小于或者等于新元素的位置，将其插到合适的位置
4.重复23,移动已排序的元素,将新的元素，放在合适的位置
 * 插入排序的复杂度
 * 插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。
 * 最优的情况，当待排序数组是有序时，只需当前数跟前一个数比较一下就可以了，N-1 轮每次比较1次，时间复杂度为 O(N)。
 * 最坏的情况  待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。
*/
function insertSort($arr) {
	$n = count($arr);
	for ($i=1;$i<$n;$i++) {
		$j=$i;
		$x = $arr[$j];
		while( $j>0 && $x < $arr[$j-1]) {
			$arr[$j] = $arr[$j-1]; //后移
			if ($j>=1) {
				$j--;
			} else {
				break;
			}
		}
		$arr[$j] = $x; //将其放到合适的位置
		print_r($arr);
	}
	return $arr;
}


$arr = array(10,6,3,8,1,5,12,21,10,2);
//$arr = quickSort($arr);
//$arr = bubble($arr);
//$arr = changesort($arr);
//$arr = cQuick($arr,0, count($arr)-1);

$arr=[2,1];
$arr = mergeSort($arr);
//$arr = insertSort($arr);
echo "<pre>";
print_r($arr);
echo "</pre>";